<h2>Problem 186</h2>
<div style="color:#666;font-size:80%;">15 March 2008</div><br />
<div class="problem_content">
<p>Here are the records from a busy telephone system with one million users:</p>
<div style='text-align:center;'>
<table cellspacing='0' cellpadding='2' border='1' align='center'>
<tr style='background-color:#c1daf9;'>
<td>RecNr</td><td width='60' align='center'>Caller</td><td width='60' align='center'>Called</td></tr>
<tr><td align='center'>1</td><td align='center'>200007</td><td align='center'>100053</td></tr>
<tr><td align='center'>2</td><td align='center'>600183</td><td align='center'>500439</td></tr>
<tr><td align='center'>3</td><td align='center'>600863</td><td align='center'>701497</td></tr>
<tr><td align='center'>...</td><td align='center'>...</td><td align='center'>...</td></tr>
</table>
</div>
<p>The telephone number of the caller and the called number in record n are Caller(n) = S<img src="" style="display:none;" alt="_(" /><sub>2n-1</sub><img src="" style="display:none;" alt=")" /> and Called(n) = S<img src="" style="display:none;" alt="_(" /><sub>2n</sub><img src="" style="display:none;" alt=")" /> where S<img src="" style="display:none;" alt="_(" /><sub>1,2,3,...</sub><img src="" style="display:none;" alt=")" /> come from the "Lagged Fibonacci Generator":</p>

<p>For 1 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> k <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 55, S<img src="" style="display:none;" alt="_(" /><sub>k</sub><img src="" style="display:none;" alt=")" /> = [100003 - 200003k + 300007k<img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" />] (modulo 1000000)<br />
For 56 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> k, S<img src="" style="display:none;" alt="_(" /><sub>k</sub><img src="" style="display:none;" alt=")" /> = [S<img src="" style="display:none;" alt="_(" /><sub>k-24</sub><img src="" style="display:none;" alt=")" /> + S<img src="" style="display:none;" alt="_(" /><sub>k-55</sub><img src="" style="display:none;" alt=")" />] (modulo 1000000)</p>

<p>If Caller(n) = Called(n) then the user is assumed to have misdialled and the call fails; otherwise the call is successful.</p>

<p>From the start of the records, we say that any pair of users X and Y are friends if X calls Y or vice-versa. Similarly, X is a friend of a friend of Z if X is a friend of Y and Y is a friend of Z; and so on for longer chains.</p>

<p>The Prime Minister's phone number is 524287. After how many successful calls, not counting misdials, will 99% of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?</p>

</div><br />
